If dark matter is composed of neutralinos, the gamma-ray radiation produced in their annihilation offers an attractive possibility for dark matter detection. This process may contribute significantly to the extragalactic gamma-ray background (EGB) radiation, which is being measured by the FERMI satellite with unprecedented sensitivity. Using the high-resolution Millennium-II simulation of cosmic structure formation we have produced the first full-sky maps of the expected contribution of dark matter annihilation to the EGB radiation. Our maps include a proper normalization of the signal according to a specific supersymmetric model based on minimal supergravity. The new simulated maps allow a study of the angular power spectrum of the gamma-ray background from dark matter annihilation, which has distinctive features associated with the nature of the annihilation process. Our results are in broad agreement with analytic models for the gamma-ray background, but they also include higher-order correlations not readily accessible in analytic calculations and, in addition, provide detailed spectral information for each pixel. In particular, we find that color maps combining different energies can reveal the cosmic large-scale structure at low and intermediate redshifts.